SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Adaptive replacement cache</title>

</head>

Adaptive replacement cache

</h1>

</header>

Adaptive Replacement Cache (ARC) is a <a href="Page_replacement_algorithm" title="Page replacement algorithm">page replacement algorithm</a> with

better performance<a href="#cite_note-1">[1]</a> than <a href="Cache_algorithms" class="mw-redirect" title="Cache algorithms">LRU</a> (least recently used). This is accomplished by keeping track of both frequently used and recently used pages plus a recent eviction history for both. The algorithm was developed<a href="#cite_note-2">[2]</a> at the IBM <a href="Almaden_Research_Center" class="mw-redirect" title="Almaden Research Center">Almaden Research Center</a>. In 2006, IBM was granted a <a rel="nofollow" class="external text" href="https://web.archive.org/web/20170624055115/http://patft1.uspto.gov/netacgi/nph-Parser?patentnumber=6996676">patent for the adaptive replacement cache policy</a>.

<div class="mw-heading mw-heading2"><h2 id="Summary">Summary</h2></div>

Basic LRU maintains an ordered list (the cache directory) of resource entries in the cache, with the sort order based on the time of most recent access. New entries are added at the top of the list, after the bottom entry has been evicted. Cache hits move to the top, pushing all other entries down.

ARC improves the basic LRU strategy by splitting the cache directory into two lists, T1 and T2, for recently and frequently referenced entries. In turn, each of these is extended with a ghost list (B1 or B2), which is attached to the bottom of the two lists. These ghost lists act as scorecards by keeping track of the history of recently evicted cache entries, and the algorithm uses ghost hits to adapt to recent change in resource usage. Note that the ghost lists only contain metadata (keys for the entries) and not the resource data itself, i.e. as an entry is evicted into a ghost list its data is discarded. The combined cache directory is organised in four LRU lists:

<ol><li>T1, for recent cache entries.</li>

<li>T2, for frequent entries, referenced at least twice.</li>

<li>B1, ghost entries recently evicted from the T1 cache, but are still tracked.</li>

<li>B2, similar ghost entries, but evicted from T2.</li></ol>

T1 and B1 together are referred to as L1, a combined history of recent single references.

Similarly, L2 is the combination of T2 and B2.

The whole cache directory can be visualised in a single line:

<pre>. . . [ B1 <-[ T1 <-!-> T2 ]-> B2 ] . .

[ . . . . [ . . . . . . ! . .^. . . . ] . . . . ]

[ fixed cache size (c) ]

</pre>

The inner [ ] brackets indicate actual cache, which although fixed in size, can move freely across the B1 and B2 history.

L1 is now displayed from right to left, starting at the top, indicated by the ! marker. ^ indicates the target size for T1, and may be equal to, smaller than, or larger than the actual size (as indicated by !).

<ul><li>New entries enter T1, to the left of !, and are gradually pushed to the left, eventually being evicted from T1 into B1, and finally dropped out altogether.</li>

<li>Any entry in L1 that gets referenced once more, gets another chance, and enters L2, just to the right of the central ! marker. From there, it is again pushed outward, from T2 into B2. Entries in L2 that get another hit can repeat this indefinitely, until they finally drop out on the far right of B2.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Replacement">Replacement</h3></div>

Entries (re-)entering the cache (T1, T2) will cause ! to move towards the target marker ^. If no free space exists in the cache, this marker also determines whether either T1 or T2 will evict an entry.

<ul><li>Hits in B1 will increase the size of T1, pushing ^ to the right. The last entry in T2 is evicted into B2.</li>

<li>Hits in B2 will shrink T1, pushing ^ back to the left. The last entry in T1 is now evicted into B1.</li>

<li>A cache miss will not affect ^, but the ! boundary will move closer to ^..</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Deployment">Deployment</h2></div>

ARC is currently deployed in IBM's DS6000/<a href="IBM_DS8000" class="mw-redirect" title="IBM DS8000">DS8000</a> storage controllers.

<a href="Sun_Microsystems" title="Sun Microsystems">Sun Microsystems</a>'s scalable file system <a href="ZFS" title="ZFS">ZFS</a> uses a variant<a href="#cite_note-3">[3]</a> of ARC as an alternative to the traditional <a href="Solaris_(operating_system)" class="mw-redirect" title="Solaris (operating system)">Solaris</a> filesystem page cache in virtual memory. It has been modified to allow for locked pages that are currently in use and cannot be vacated.

<a href="PostgreSQL" title="PostgreSQL">PostgreSQL</a> used ARC in its buffer manager for a brief time (version 8.0.0), but quickly replaced it with another algorithm,

citing concerns over an IBM patent on ARC.<a href="#cite_note-4">[4]</a>

<a href="VMware" title="VMware">VMware</a>'s vSAN (formerly Virtual SAN) is a hyper-converged, software-defined storage (SDS) product developed by VMware. It uses A variant of ARC in its Caching Algorithm. <a href="#cite_note-5">[5]</a>

<a href="OpenZFS" title="OpenZFS">OpenZFS</a> supports using ARC and L2ARC in a <a href="Multi-level_cache" class="mw-redirect" title="Multi-level cache">multi-level cache</a> as read caches.

In OpenZFS, disk reads often hit the first level disk cache in RAM using ARC.

If a SSD is set up to store the second level disk cache, it is called an L2ARC. L2ARC uses the same ARC algorithm, but instead of storing the cached data in RAM, L2ARC stores the cached data in a fast SSD.<a href="#cite_note-6">[6]</a><a href="#cite_note-7">[7]</a><a href="#cite_note-8">[8]</a><a href="#cite_note-9">[9]</a><a href="#cite_note-10">[10]</a><a href="#cite_note-11">[11]</a>

<ul><li><a href="Clock_with_Adaptive_Replacement" class="mw-redirect" title="Clock with Adaptive Replacement">Clock with Adaptive Replacement</a></li>

<li><a href="LIRS_caching_algorithm" title="LIRS caching algorithm">LIRS caching algorithm</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<li id="cite_note-1"><a href="#cite_ref-1">^</a> One Up on LRU, <a rel="nofollow" class="external text" href="https://www.usenix.org/publications/login/august-2003-volume-28-number-4/one-lru">Usenix :login; August 2003</a>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <a href="Nimrod_Megiddo" title="Nimrod Megiddo">Nimrod Megiddo</a> and <a href="Dharmendra_Modha" title="Dharmendra Modha">Dharmendra Modha</a>, <a rel="nofollow" class="external text" href="https://web.archive.org/web/20100329071954/http://www.almaden.ibm.com/StorageSystems/projects/arc/">2010-03-09 archive of the ARC home page</a>, with pointers to several articles

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> comments in Solaris ZFS <a rel="nofollow" class="external text" href="https://archive.today/20130703061815/http://java.net/projects/solaris/sources/on-src/content/usr/src/uts/common/fs/zfs/arc.c?rev=13149">arc.c </a> source file explains differences with original work

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> Article in Postgresql General Bits, <a rel="nofollow" class="external text" href="https://archive.today/20130205145832/http://www.varlena.com/GeneralBits/96.php">"The Saga of the ARC Algorithm and Patent"</a>, published 6 February 2005

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> Reference document, <a rel="nofollow" class="external text" href="https://www.storagehub.vmware.com/t/vmware-vsan/vmware-vsan-caching-algorithms/">"VMware vSAN Caching Algorithms"</a>

</li>

<a rel="nofollow" class="external text" href="https://www.45drives.com/community/articles/zfs-caching/">"ZFS Caching"</a>.

</li>

<a rel="nofollow" class="external text" href="https://www.ixsystems.com/documentation/freenas/11.3-U5/zfsprimer.html">"ZFS Primer"</a>.

</li>

Jim Salter.

<a rel="nofollow" class="external text" href="https://arstechnica.com/gadgets/2020/02/zfs-on-linux-should-get-a-persistent-ssd-read-cache-feature-soon/">"Persistent L2ARC might be coming to ZFS on Linux"</a>.

2020.

</li>

<a rel="nofollow" class="external text" href="https://docs.oracle.com/cd/E27998_01/html/E48490/analytics__statistics__cache_l2arc_accesses.html">"Cache: L2ARC accesses"</a>.

</li>

Brendan Gregg.

<a rel="nofollow" class="external text" href="http://www.brendangregg.com/blog/2008-07-22/zfs-l2arc.html">"ZFS L2ARC"</a>.

</li>

Ranvir Singh.

<a rel="nofollow" class="external text" href="https://linuxhint.com/configuring-zfs-cache/">"Adaptive Replacement Cache (ARC) and L2ARC"</a>.

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.5210">ARC: A Self-Tuning, Low Overhead Replacement Cache (2003) by Nimrod Megiddo, Dharmendra Modha</a></li>

<li><a rel="nofollow" class="external text" href="http://linux-mm.org/AdvancedPageReplacement">Linux Memory Management Wiki</a></li>

<li>Bourbonnais, Roch. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20120902124517/https://blogs.oracle.com/roch/date/20060621">ZFS Dynamics</a></li>

<li><a rel="nofollow" class="external text" href="http://code.activestate.com/recipes/576532/">Python implementation, recipe 576532</a></li>

<li><a rel="nofollow" class="external text" href="http://www.cs.biu.ac.il/~wiseman/2os/2os/os2.pdf">Comparison of LRU, ARC and others</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-12-16" href="https://en.wikipedia.org/wiki/?title=Adaptive_replacement_cache&oldid=1263388679">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>